package MyQueue;

import Stack.isEmptyException;

import java.util.Iterator;
import java.util.Stack;

public class MyQueue {



       static class ListNode{
           public  int val;
           public ListNode next;
           public ListNode prev;

           public ListNode(int val) {
               this.val = val;
           }
       }

       public ListNode head;
       public ListNode last;

       //入队
       public void offer(int val){

           ListNode node=new ListNode(val);
           if(this.head==null){
               head=node;
               last=node;
           }else{
               last.next=node;
               node.prev=last;
               last=node;
           }

       }

       //出队
       public int poll(){
            if(isEmpty()){
               throw new isEmptyException("空栈异常");
            }
            int val=head.val;
            if(head.next==null){

                head=null;
                last=null;
                return val;
            }
            head=head.next;
            head.prev=null;
            return val;
       }

       public boolean isEmpty(){
           return head==null;
       }
       //获取出队元素
       public int peek(){
           if(isEmpty()){
               throw new isEmptyException("空栈异常");
           }
           return head.val;
       }
       
       public void display(){
           ListNode cur=head;
           while(cur!=null){
               System.out.print(cur.val+" ");
               cur=cur.next;
           }
       }

    /*
     *https://leetcode.cn/problems/implement-queue-using-stacks/description/
     * 2. 用栈实现队列
     * */
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue() {
        this.stack1=new Stack<>();
        this.stack2=new Stack<>();
    }

    public void push(int x) {
        if(empty()){
            stack1.push(x);
        }else{
            stack2.push(x);
        }
    }

    public int pop() {
        if(!stack1.isEmpty()){
            return stack1.pop();
        }else{

            if(stack2.isEmpty()){
                return -1;
            }
            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
        }
        return stack1.pop();
    }

    public int peek1() {
        if(!stack1.isEmpty()){
            return stack1.peek();
        }else{

            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
        }
        return stack1.peek();
    }

    public boolean empty() {

        return stack1.isEmpty() && stack2.isEmpty();
    }

}
